int partSort3(int* a, int begin, int end)
{
	int mid = GetMid(a, begin, end);
	swap(&a[mid], &a[begin]);

	int prev = begin;
	int cur = begin + 1;
	int key = begin;
	/*while (cur <=end)
	{
		if (a[cur] >= a[key])
		{
			cur++;
		}
		else
		{
			prev++;
			if (prev != cur)
			{
				swap(&a[prev], &a[cur]);
			}
			cur++;
		}
	}
	swap(&a[key], &a[prev]);
	return prev;*/

	//优化:
	while (cur <= end)
	{
		if (a[cur] < a[key] && ++prev != end)
			swap(&a[prev], &a[cur]);
		++cur;
	}
	swap(&a[key], &a[prev]);
	return prev;
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	if (end - begin + 1 <= 10)
	{
		InsertSort(a + begin, end - begin + 1);
	}
	else
	{

		//int keyi = pratSort1(a, begin, end);
		int keyi = partSort3(a, begin, end);
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
}

void QuickSortNonR(int* a, int begin, int end)
{
	ST s;
	STInit(&s);
	STPush(&s, end);
	STPush(&s, begin);

	while (!STEmpty(&s))
	{
		int left = STTop(&s);
		STPop(&s);
		int right = STTop(&s);
		STPop(&s);

		int keyi = partSort3(a, left, right);
		
		if (left < keyi - 1)
		{
			STPush(&s, keyi - 1);
			STPush(&s, left);
		}

		if (keyi + 1 < right)
		{
			STPush(&s, right);
			STPush(&s, keyi + 1);
		}
	}
}